#include "heap.h"
void adjustHeap(int *a, int root, int n) {
  int leftChild = (root << 1) + 1;
  int rightChild = leftChild + 1;
  int maxIndex = root;
  if (leftChild <= n && a[leftChild] > a[root])
    maxIndex = leftChild;
  if (rightChild <= n && a[rightChild] > a[maxIndex])
    maxIndex = rightChild;
  if (maxIndex != root) {
    swap(a[root], a[maxIndex]);
    adjustHeap(a, maxIndex, n);
  }
}
void buildHeap(int *a, int n) {
  int mid = (n >> 1);
  for (int root = mid; root >= 0; root--) {
    adjustHeap(a, root, n);
  }
}
vector<int> heapSort(int *a, int n) {
  vector<int> res;
  for (int i = n - 1; i > 1; i--) {
    buildHeap(a, i);
    swap(a[0], a[i]);
    res.push_back(a[i]);
  }
  res.push_back(a[1]);
  res.push_back(a[0]);
  return res;
}